package GreedyAlgorithm;

/**
 * @author Liaorun
 */
public class MaxSquareSideInMatrix {

    public static void main(String[] args) {
        int[][] test = {{1, 1, 1}, {1, 0, 0}, {0, 0, 0}};

        System.out.println(maxSquareSideInMatrix(test));
    }

    public static int maxSquareSideInMatrix(int[][] m) {
        int rows = m.length;
        int cols = m[0].length;

        // 记录最大正方形的边长,默认整个矩阵没有一个1的情况，正方形的边长为0
        int maxSide = 0;

        // 记录每个位置右侧和下侧连续1的个数
        int[][] right = new int[rows][cols];
        int[][] down = new int[rows][cols];


        for (int row = 0; row < rows; row++) {
            for (int col = cols - 1; col >= 0; col--) {
                if (col < cols - 1) {
                    if (m[row][col] == 1) {
                        // 右边有数，右边连续的1就自己一个 + 左边连续的数量
                        right[row][col] = 1 + right[row][col + 1];
                    }
                } else {
                    if (m[row][col] == 1) {
                        // 右边没有数，右边连续的1就自己一个
                        right[row][col] = 1;
                    }
                }
            }
        }

        for (int row = rows - 1; row >= 0; row--) {
            for (int col = 0; col < cols; col++) {
                if (row < rows - 1) {
                    if (m[row][col] == 1) {
                        // 下边有数，下边连续的1就自己一个 + 下边连续的数量
                        down[row][col] = 1 + down[row + 1][col];
                    }
                } else {
                    if (m[row][col] == 1) {
                        // 下边没有数，右边连续的1就自己一个
                        down[row][col] = 1;
                    }
                }
            }
        }


        // 遍历每个点去尝试
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                // 枚举边长,最大的边长是当前点到矩阵边界最短的直线距离

                for (int side = 0; side < Math.min(rows - row, cols - col); side++) {
                    // 验证当前正方形的四条边上的值都为1

                    if (right[row][col] >= side + 1 && down[row][col] >= side + 1) {
                        // 左上两条边满足的情况下，验证另外两条边
                        if (down[row][col + side] >= side + 1) {
                            // 右边满足，检查下边
                            if (right[row + side][col] >= side + 1) {
                                // 是一个正方形，检查是不是最大边长
                                maxSide = Math.max(side + 1, maxSide);
                            }
                        }
                    }
                }
            }
        }

        return maxSide;
    }
}
